Polynomial Rings¶

$ R[x]=\left\{a_{0}+a_{1} x+a_{2} x^{2}+\cdots+a_{n} x^{n}: n \geq 0 \text { and } a_{0}, a_{1}, \ldots, a_{n} \in R\right\} $

The degree of a nonzero polynomial is the exponent of the highest power of $x$ that appears. Thus if $ \boldsymbol{a}(x)=a_{0}+a_{1} x+a_{2} x^{2}+\cdots+a_{n} x^{n} $ with $a_{n} \neq 0,$ then $\boldsymbol{a}(x)$ has degree $n .$

We denote the degree of $\boldsymbol{a}$ by $\operatorname{deg}(\boldsymbol{a})$ and we call $a_{n}$ the leading coefficient of $\boldsymbol{a}(x)$.

A nonzero polynomial whose leading coefficient is equal to 1 is called a monic polynomial. For example,

In [28]:

def poly_gcd(a, b):
    if(b.is_zero()):
        return a
    else:
        return poly_gcd(b, a%b)

In [92]:

def poly_egcd(a, b):
    if(a.is_zero()):
        return (b, 0, 1)
    else:
        gcd, x, y = poly_egcd(a%b, a)
        return (gcd, y-(b // a) * x, x)

In [93]:

F.<x> = PolynomialRing(GF(13))

In [94]:

a = x**5 - 1
b = x**3 + 2*x - 3

In [95]:

poly_gcd(a, b)

Out[95]:

9*x + 4

In [96]:

F.<x> = PolynomialRing(GF(2))
a = x**5 + 3 * x ** 4 - 5 * x **3 -3 * x **2 + 2 * x + 2
b = x**5 + x ** 4 - 2 * x **3 + 4 * x**2 +x + 5

In [97]:

poly_egcd(a,b)

Out[97]:

(x^3 + x^2 + x + 1, x^2 + 1, x^2)

In [85]:

xgcd(a, b)

Out[85]:

(x^3 + x^2 + x + 1, 1, 1)

Polynomials modulo polynomials haha funny¶

Let $\mathbb{F}$ be field and let $\boldsymbol{m} \in \mathbb{F}[x]$ be a nonzero polynomial. Then every nonzero congruence class $\overline{\boldsymbol{a}} \in \mathbb{F}[x] /(\boldsymbol{m})$ has a unique representative $\boldsymbol{r}$ satisfying
$ \operatorname{deg} \boldsymbol{r}<\operatorname{deg} \boldsymbol{m} \quad \text { and } \\ \boldsymbol{a} \equiv \boldsymbol{r}(\bmod \boldsymbol{m}) $

Let $\mathbb{F}$ be a field and let $a, m ∈ \mathbb{F}[x]$ be polynomials with $m != 0$. Then $\overline{a}$ is a unit in the quotient ring $\mathbb{F}[x]/(m)$ if and only if
$gcd(a, m) = 1$

In [43]:

F.<x> = PolynomialRing(GF(2))
Fm.<y> = F.quotient(x**3+x+1) 

In [52]:

len(Fm)

Out[52]:

Let $\mathbb{F}_p$ be a finite field.
(a) For every d ≥ 1 there exists an irreducible polynomial $m ∈ \mathbb{F}_p[x]$ of degree d.
(b) For every d ≥ 1 there exists a finite field with pd elements.
(c) If F and F are finite fields with the same number of elements, then there is a way to match the elements of $\mathbb{F}$ with the elements of $\mathbb{F}'$ so that the addition and multiplication tables of $\mathbb{F}$ and $\mathbb{F'}$ are the same.

(The mathematical terminology is that $\mathbb{F}$ and $\mathbb{F'}$ are isomorphic.) $

In [ ]: